package xin.yangshuai.leetcode01.question37;

//编写一个程序，通过填充空格来解决数独问题。
//
//数独的解法需 遵循如下规则：
//
//    数字 1-9 在每一行只能出现一次。
//    数字 1-9 在每一列只能出现一次。
//    数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
//
//数独部分空格内已填入了数字，空白格用 '.' 表示。
//
//
//
//示例 1：
//
//输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
//输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
//解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
//
//
//
//
//提示：
//
//    board.length == 9
//    board[i].length == 9
//    board[i][j] 是一位数字或者 '.'
//    题目数据 保证 输入数独仅有一个解

import java.util.ArrayList;
import java.util.List;

public class Question37 {

    public static void main(String[] args) {
        Solution solution = new Question37().new Solution();
        char[][] board = {
                {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}};
        solution.solveSudoku(board);
        for (char[] chars : board) {
            for (char aChar : chars) {
                System.out.print(aChar + "\t");
            }
            System.out.println();
        }
    }

    class Solution {
        public void solveSudoku(char[][] board) {

            // 把唯一确定的值先填上
            boolean fillInFlag = true;

            while (fillInFlag) {

                fillInFlag = false;
                for (int i = 0; i < board.length; i++) {
                    for (int j = 0; j < board[i].length; j++) {
                        if ('.' == board[i][j]) {
                            List<Character> charList = new ArrayList<>();
                            charList.add('1');
                            charList.add('2');
                            charList.add('3');
                            charList.add('4');
                            charList.add('5');
                            charList.add('6');
                            charList.add('7');
                            charList.add('8');
                            charList.add('9');
                            // 判断当前行的值
                            for (int k = 0; k < 9; k++) {
                                char c = board[i][k];
                                if (c != '.') {
                                    charList.remove(new Character(c));
                                }
                            }
                            // 判断当前列的值
                            for (int k = 0; k < 9; k++) {
                                char c = board[k][j];
                                if (c != '.') {
                                    charList.remove(new Character(c));
                                }
                            }
                            // 判断当前九宫格的值
                            int i1 = (i / 3) * 3;
                            int j1 = (j / 3) * 3;
                            for (int k = i1; k < i1 + 3; k++) {
                                for (int l = j1; l < j1 + 3; l++) {
                                    char c = board[k][l];
                                    if (c != '.') {
                                        charList.remove(new Character(c));
                                    }
                                }
                            }
                            if (charList.size() == 1) {
                                Character character = charList.get(0);
                                board[i][j] = character;
                                System.out.println(String.format("board[%s][%s]=%s", i, j, character));
                                fillInFlag = true;
                            }
                        }
                    }
                }
            }
            solveSudoku(board, 0, 0);
        }

        public boolean solveSudoku(char[][] board, int i, int j) {
            int iTemp = i;
            int jTemp = j;
            for (; i < board.length; i++) {
                for (; j < board[i].length; j++) {
                    if ('.' == board[i][j]) {
                        List<Character> charList = new ArrayList<>();
                        charList.add('1');
                        charList.add('2');
                        charList.add('3');
                        charList.add('4');
                        charList.add('5');
                        charList.add('6');
                        charList.add('7');
                        charList.add('8');
                        charList.add('9');
                        // 判断当前行的值
                        for (int k = 0; k < 9; k++) {
                            char c = board[i][k];
                            if (c != '.') {
                                charList.remove(new Character(c));
                            }
                        }
                        // 判断当前列的值
                        for (int k = 0; k < 9; k++) {
                            char c = board[k][j];
                            if (c != '.') {
                                charList.remove(new Character(c));
                            }
                        }
                        // 判断当前九宫格的值
                        int i1 = (i / 3) * 3;
                        int j1 = (j / 3) * 3;
                        for (int k = i1; k < i1 + 3; k++) {
                            for (int l = j1; l < j1 + 3; l++) {
                                char c = board[k][l];
                                if (c != '.') {
                                    charList.remove(new Character(c));
                                }
                            }
                        }
                        if (charList.isEmpty()) {
                            System.out.println(String.format("board[%s][%s]可能值为空，返回false，上一步board[%s][%s]=%s", i, j, iTemp, jTemp, board[iTemp][jTemp]));
                            return false;
                        } else {
                            System.out.println(String.format("board[%s][%s]可能值=%s，上一步board[%s][%s]=%s", i, j, charList, iTemp, jTemp, board[iTemp][jTemp]));
                            for (Character character : charList) {
                                board[i][j] = character;
                                System.out.println(String.format("board[%s][%s]尝试=%s，上一步board[%s][%s]=%s", i, j, character, iTemp, jTemp, board[iTemp][jTemp]));
                                boolean b = solveSudoku(board, i, j);
                                if (b) {
                                    System.out.println(String.format("board[%s][%s]=%s，正确，返回true，上一步board[%s][%s]=%s", i, j, character, iTemp, jTemp, board[iTemp][jTemp]));
                                    return true;
                                }
                                System.out.println(String.format("board[%s][%s]=%s，错误，尝试下一个，上一步board[%s][%s]=%s", i, j, character, iTemp, jTemp, board[iTemp][jTemp]));
                            }
                            board[i][j] = '.';
                            System.out.println(String.format("board[%s][%s]=.，无值可尝试，设置为.，返回false，上一步board[%s][%s]=%s", i, j, iTemp, jTemp, board[iTemp][jTemp]));
                            return false;
                        }
                    }
                }
                j = 0;
            }
            return true;
        }
    }
}
